package com.monkey.algorithm.chapter1.stack

/**
 * 作者：Monkey
 * 日期：2018/1/26
 */
class ResizeingArrayStack<T> : Iterable<T> {
    private var n = 0

    private var items = Array<Any?>(1) { null } as Array<T?>

    fun size() = n

    fun isEmpty() = n == 0

    /**
     * 入栈
     * @param item 要入栈的元素
     */
    fun push(item: T) {
        // 判断栈是否已满，如果已满resize
        if (isFull()) {
            resize(items.size * 2)
        }

        // 入栈
        items[n++] = item
    }

    /**
     * 出栈
     */
    fun pop(): T {
        // 出栈
        val item = items[n--]
        items[n] = null

        // 判断栈是否空闲，如果空闲resize
        val min = items.size / 4
        if (n < min) {
            resize(min)
        }

        return item!!
    }

    /**
     * 判断栈是否已满
     */
    private fun isFull() = n == items.size

    /**
     * @param max 数组将被设置的大小
     */
    private fun resize(max: Int) {
        items = items.copyOf(max)
    }

    override fun iterator(): Iterator<T> {
        return ReverseArrayIterator()
    }

    private inner class ReverseArrayIterator : Iterator<T> {
        private var index = 0

        override fun hasNext() = index != n

        override fun next(): T = items[index++]!!
    }
}